---
title: "海战"
created: 2025-11-28
tags:
  - 算法
---

# 海战

## 题目 [海战](https://www.luogu.com.cn/problem/P1331)

![[image-4ff3cdfe.png]]

## 思路分析

这道题的难点在于判断是否有船相邻。 如果图是不和法的，一定存在如下结构：

# #

. #

# #

# .

# .

# #

. #

# #

即在一个2\*2的方格中有三个#

洛谷太傻逼了 一堆runtime error

下面这个写法不是用洪水灌溉

有个想法是 先用洪水灌溉找到连通块 再对每一个连通块进行拆解？

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N=1010;

char g[N][N];

int n,m;

int dx[4]={0,-1,1,0};

int dy[4]={-1,0,0,1};

bool isVaild(int x,int y){

	return x>=1 && x<=n && y>=1 && y<=m;

}

int dfs(int x,int y){

	g[x][y]='*';

	for(int i=0;i<4;i++){

		int nx=x+dx[i],ny=y+dy[i];

		if(isVaild(nx,ny) && g[nx][ny]=='#')

			dfs(nx,ny);

	}

}

bool check(int i,int j){

	int c=0;

	if(g[i][j]=='#')

		c++;

	if(g[i+1][j]=='#')

		c++;

	if(g[i][j+1]=='#')

		c++;

	if(g[i+1][j+1]=='#')

		c++;

	if(c==3)

		return false;

	return true;

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++)

			cin>>g[i][j];

	int s=0;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			if(i<n && j<m && !check(i,j)){

				cout<<"Bad placement.";

				return 0;

			}

		}

	}

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			if(g[i][j]=='#'){

				s++;

				dfs(i,j);

			}

		}

	}

	cout<<"There are "<<s<<" ships.";

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[家族|家族]] 🏠 [[00-刷题理模型]] ➡️ [[多源BFS|多源BFS]]